; >FileCore31

; *********************************
; ***  CHANGE LIST AND HISTORY  ***
; *********************************
;
; 16-Jun-94   AMcC  Replaced ScratchSpaceSize with ?ScratchSpace
;
; 08-Sep-94   SBP   Added AMG's fix to NewClaimFree
;

 [ NewFs

        TTL     "New map allocation"



NewClaimFree ROUT
 [ DebugE
        DREG    R3, "NewClaimFree(",cc
        DREG    R5, ",",cc
        DREG    R6, ",",cc
        DREG    R10, ",",cc
        DREG    R11, ",",cc
        DLINE   ")"
 ]

        MOV     R1, LR                  ;->disc rec
        BCS     NewRandomClaim
        SUBS    R0, R10,#0              ;V=0
        ANDEQ   R2, R3, #DiscBits       ;zero length request
        ORREQ   R2, R2, #1              ;useful to treat 0 length as shared obj
        MOVLT   R0, #DiscFullErr
        BLE     %FT93
        MOV     R9, R0
        BL      RoundUp                 ;(R0,R3->R0)
        LDRB    LR, [R1,#BitSize]
        MOV     R4, R0, LSR LR

        ASSERT  fsfile_CreateDir=UnsharedCreate
        TEQS    R11,#UnsharedCreate
        BL      CritInitReadNewFs       ;(->R10,R11)
        LDREQB  R0, [R10,#ZoneHead+Zones]
        MOVEQ   R0, R0, LSR #1          ;dir search starts from central map zone
        BEQ     %FT09                   ;a dir can't share with existing objects

        BL      AllocBitWidth   ;(R10->LR)
        MOV     R0, LR
        BL      MinMapObj       ;(R10->LR)
        SUB     LR, LR, R0
        CMPS    R4, LR, LSL #1
        BHI     %FT08           ;too big to share a map obj
        Push    "R4"
        BL      SortDir         ;(R3,R5->R8)

;Find smallest suitable space (if any) in shared fragments
;R0 temp                        ;R4 dir offset          ;R8  -> sorted list
;R1 end sector prev obj in frag ;R5 link bits           ;R9  len needed in secs
;R2 best disc address           ;R6 smallest fit        ;R10 -> map start
;R3 dir                         ;R7 log2 sector size    ;R11 sec size - 1

        MOV     R6, #8*K        ;init smallest fit
        LDRB    R7, [R10,#ZoneHead+SectorSize]
 [ BigShare
        LDRB    LR, [R10, #ZoneHead+ShareSize]  ; get sharing unit
        ADD     R7, R7, LR                      ; get overall sharing size (sectors*sharing unit)
 ]
        MOV     R11,#1
        RSB     R11,R11,R11,LSL R7
        TSTS    R9, R11
        MOV     R9, R9, LSR R7
        ADDNE   R9, R9, #1      ;sharing blocks needed
02
        MOV     R1, #1          ;init end sector offset of prev obj in frag
04                      ;NOW EXAMINE EACH SHARED OBJ IN DIR IN ORDER
        LDRB    R4, [R8]        ;index in dir
        LDRB    R0, [R8,#1]     ;sharing offset in frag
        LDR     R5, [R8],#4
        TEQS    R5, #0
        BEQ     %FT06           ;end of list marker found
        MOVS    R5, R5, LSR #17 ;link bits
        ADDCS   R5, R5, R3, LSR #8
        RSBCC   R5, R5, R3, LSR #8
 [ DebugE
        DREG    R0, "File sector:",cc
        DREG    R1, ", pre gap sector:",cc
        DREG    R4, ", file index:",cc
        DREG    R5, ", link bits:"
 ]

        TEQS    R4, #0
        BEQ     %FT05           ;any spare shared before dir is map or boot
        SUB     LR, R0, R1      ;gap before frag
        CMPS    R9, LR          ;IF size needed <= gap
        CMPLS   LR, R6          ;AND gap<smallest

        MOVLO   R6, LR          ;THEN note new smallest
        ANDLO   R2, R3, #DiscBits
        ORRLO   R2, R2, R5, LSL #8
        ORRLO   R2, R2, R1
 [ DebugE
        BHS     %FT01
        DREG    R2, "smaller pre gap in shared frag - ind disc add:",cc
        DREG    R6, ", size:"
01
 ]
05
        ASSERT  NewDirEntrySz=26
        ADDS    LR, R4, R4, LSL #1      ;R4*3 convert index in dir to ptr
        ADDNE   R4, R4, LR, LSL #2      ;R4*13
        sbaddr  LR, (DirBuffer+DirFirstEntry-NewDirEntrySz),NE
        ADDNE   R4, LR, R4, LSL #1      ;ptr to dir entry
        BL      ReadLen                 ;(R3,R4->LR)    R4=0 if dir itself
        TSTS    LR, R11
        ADD     R1, R0, LR, LSR R7      ;inc end sector offset past obj
        ADDNE   R1, R1, #1

        SUB     R0, R8, #4
        LDMIA   R0, {R0,LR}
        EOR     LR, R0, LR
        MOVS    LR, LR, LSR #16
        BEQ     %BT04                   ;IF next obj in same frag then loop

        MOV     R0, R5, LSL #8          ;ELSE consider gap after obj
        Push    "R2,R5,R9"
        AND     R2, R3, #DiscBits
        ORR     R2, R2, R5, LSL #8      ;ind disc address of shared frag start
        MOV     R5, #0
        BL      DefFindFileFragment     ;(R2,R5->R2,R4,R5,R9,LR)
        Pull    "R2,R5,R9"
        RSB     LR, R1, R4, LSR R7
        ADD     LR, LR, #1              ;since sector offsets start at 1

        CMPS    R9, LR          ;consider gap as before
        CMPLS   LR, R6

        MOVLO   R6, LR
        ANDLO   R2, R3, #DiscBits
        ORRLO   R2, R2, R5, LSL #8
        ORRLO   R2, R2, R1

 [ DebugE
        BHS     %FT01
        DREG    R2, "smaller post gap in shared frag - ind disc add:",cc
        DREG    R6, ", ind disc add:"
01
 ]
        TEQS    R6, #8*K
        BEQ     %BT02           ;loop if no fit found

06
        Pull    "R4"
        TEQS    R6, #8*K
 [ DebugE
        BEQ     %FT01
        DLINE   "space found in shared fragment"
01
 ]
        BNE     %FT91

 ^ 0,SP
FragZone        # 4
NextZone        # 4
ZonesLeft       # 4
FragScore       # 4
AllocWork1      # 0

08
        LDR     LR, [SP,#ClaimReason]       ;entry reason code
        TEQS    LR, #CloseSmall
        MOVEQ   R0, #DiscFullErr
        BEQ     %FT93
        MOV     R0, R3
        BL      IndDiscAddToZone        ;(R0,R10->R0)
09
        SUB     R1, R0, #1
        LDRB    R2 ,[R10,#ZoneHead+Zones]
        MOV     R7, #0
        Push    "R0,R1,R2,R7"
        MOV     R1, #-1
        BL      MinMapObj       ;(R10->LR)
        MOV     R8, LR
;R0 zone                R4 size needed in map bits      R8 min map obj
;R1 smallest good gap   R5 total free                   R9-R11 map
;R2 zone free<<9 + gaps R6 predecessor of best gap
;R3 top 3 bits disc     R7 length

        MOV     R5, #0
10
        BL      InitZoneFree    ;(R0,R10->R11)
        MOV     R2,#0
12
        BL      NextFree        ;(R10,R11->R9, R11,Z,C)
        BLNE    RdLenBits       ;(R10,R11->R7)
        BCS     %FT14           ;zone done
        ADD     R5, R5, R7
        ADD     R2, R2, R7,LSL #9
        ADD     R2, R2,#1
        SUBS    LR,R7, R4
        CMPHS   R1, R7
        BLS     %BT12           ;loop unless smallest > gap >= obj size

        CMPS    R7, R8,LSL #1    ;IF gap small enough to share
        TEQS    LR,#0           ;OR exact fit
        CMPHIS  R8,LR           ;OR no waste
 [ DebugE
        BHI     %FT01
        DREG    R7, "better fit - size:",cc
        DREG    R9, ", pre gap:"
01
 ]
        MOVLS   R1, R7           ;note better gap
        MOVLS   R6, R9
        B       %BT12
14
        CMPS    R1, #-1
        ADDNE   SP, SP, #:INDEX:AllocWork1
        BNE     %FT90           ;if found a suitable gap in this zone
        MOV     R7, R2,LSR #9    ;total free in zone
        SUB     R2, R2, R7,LSL #9 ;gaps in zone
        SUBS    R2, R2,#1
        MULGT   R9, R7, R2        ;free in zone * (gaps-1)
        LDRGT   LR,FragScore
        CMPGTS  R9, LR          ;IF this zone has a higher fragmentation score
        BLE     %FT16
        BL      ZoneFlagsPtr    ;(R10->LR)
        LDRB    LR, [LR,R0]
        TSTS    LR, #ZoneCompacted      ;AND not fully compacted
 [ DebugE
        BEQ     %FT01
        DLINE   "Zone Compacted"
01
 ]
 [ DebugE
        DREG    R0, "better zone for compaction - ",cc
        DREG    R9, ","
 ]
        STREQ   R9, FragScore            ;THEN note new zone for compaction
        STREQ   R0, FragZone
16
        LDR     LR, ZonesLeft
        SUBS    LR, LR, #1
        BLE     %FT18
        STR     LR, ZonesLeft
17                              ;try next zone
        LDR     LR, NextZone
        CMPS    R0, LR
        ADDGE   R0, R0, #1
        SUBLT   R0, R0, #1
        STR     R0, NextZone
        MOV     R0, LR
        CMPS    R0, #-1
        LDRGTB  LR, [R10,#ZoneHead+Zones]
        CMPGTS  LR, R0
        BLE     %BT17           ;if bad zone number
        B       %BT10

18                              ;HERE IF FAILED TO FIND USEFUL GAP IN ANY ZONE
        ASSERT  :INDEX: FragZone   = 0
        ASSERT  :INDEX: FragScore  = 12
        ASSERT  :INDEX: AllocWork1 = 16
        Pull    "R0,R1,R2,LR"

        CMPS    R4, R5           ;IF space needed>total free then full
        ASSERT  fsfile_Create>fsfile_Save
        ASSERT  CloseSmall>fsfile_Create
        ASSERT  CloseContig>fsfile_Create
        LDRLS   R1, [SP,#ClaimReason]
        CMPLS   R1, #fsfile_Create        ;OR if close case
        MOVHI   R0, #DiscFullErr
        BHI     %FT93

 [ DebugE
        DLINE   "no gap big enough for whole file"
 ]

        CMPS    LR, #0          ;V=0
        MOVNE   R1, R4
        BLNE    DefCompactZone  ;(R0,R1,R10->R0,R2,V)
        BVS     %FT95

WasteBit        bit 31
MultiBit        bit 30

        MOV     R11,#FreeLink*8
        BL      Log2AllocBits   ;(->LR)
        MOV     R2, LR

        ASSERT  ?ScratchSpace>=16*K
        MOV     R0, #ScratchSpace
        LDRB    R1, [R10,#ZoneHead+SectorSize]
        MOV     R5, #8*2
        MOV     R1, R5,LSL R1
        MOV     R1, R1,LSR R2
        BL      ZeroRam         ;init tables of gap frequencies
        ADD     R1, R0, R1,LSR #1
        MOV     R5, #0  ;init total gaps between ptrs
        MOV     R6, #-1 ;init best fit

;R1 ->gap frequency tables
;R2 log2 alloc unit bit width
;R3 dir
;R4 size needed in bits
;R5 total gap length between map ptrs
;R6 best fit
;R8 min map obj

 ^ 0,SP
AllocDir        # 4
PreBestPtr      # 4
FitType         # 4
PtrDiff         # 4
PreFirstGap     # 4
FirstGap        # 4
LastGap         # 4
LastSize        # 4
AllocWork2      # 0

        Push    "R3, R7-R13"      ;save dir & reserve stack space
        BL      NextFree        ;(R10,R11->R9, R11,Z,C)
        BLNE    RdLenBits       ;(R10,R11->R7)
        STR     R9, PreFirstGap
        STR     R11,FirstGap
        B       %FT32
30
        BL      NextFree        ;(R10,R11->R9, R11,Z,C)
        BLNE    RdLenBits       ;(R10,R11->R7)
32
        BEQ     %FT58           ;all tried
        STR     R7, LastSize
        SUBS    R0, R7, R4
        BLO     %FT34           ;gap too small for obj
        CMPNES  R0, R8           ;if not exact fit can rest be made a gap
        ORRLO   R0, R0,#WasteBit
        CMPS    R0, R6
 [ DebugE
        BHS     %FT01
        DREG    R6, "single gap - fit:",cc
        DREG    R9, ", pre:"
01
 ]
        MOVLO   R6, R0
        STRLO   R9, PreBestPtr
34
        TSTS    R6, #WasteBit :OR: MultiBit
        BEQ     %BT30           ;if found single gap fit no waste

        STR     R11,LastGap
        MOV     R0, R7,LSR R2
        LDRB    LR, [R1, R0]    ;inc frequency of gaps of this size
        ADD     LR, LR,#1
        STRB    LR, [R1, R0]
        LDRB    LR, [R1,-R0]    ;inc freq of gaps of this size between map ptrs
        ADD     LR, LR, #1
        STRB    LR, [R1,-R0]
35
        SUB     LR, R4, R5      ;amount needed from this gap
        ADD     R5, R5, R7      ;adjust total gap length between map ptrs
        SUBS    R9, R4, R5
        BHI     %FT42           ;total still too small
        SUBS    R0, R8,LR
        BHI     %FT36           ;min size > amount needed
        SUBS    R0, R5, R4      ;remains of gap
        CMPNES  R0, R8
        ORRLO   R0, R0,#WasteBit
        B       %FT38
36
        CMPS    R7, R8, LSL #1  ;can this gap be split
        SUBLO   R0, R7, LR
        ORR     R0, R0, #WasteBit
38
        ORR     R0, R0, #MultiBit
        CMPS    R0, R6
        MOVLS   R7, #0          ;fit type
        BLLS    %FT50           ;if possibly better fit
40
        SUBS    R7, R5, R4      ;R7 := amount total exceeds required
        MOV     LR, R7, LSR R2
        LDRB    LR, [R1,-LR]
        TEQS    LR, #0          ;IF we are using a gap of size R7
        BLNE    %FT48           ;THEN exact fit without it

        LDR     R11,FirstGap
        BL      RdLenBits       ;(R10,R11->R7)
        SUB     R5, R5, R7
        MOV     LR, R7, LSR R2
        LDRB    R0, [R1,-LR]    ;dec freq of gaps of this size between map ptrs
        SUB     R0, R0,#1
        STRB    R0, [R1,-LR]
        BL      NextFree        ;(R10,R11->R9, R11,Z,C)
        STR     R9, PreFirstGap
        STR     R11,FirstGap
        LDR     R7, LastSize
        LDR     R11,LastGap
        SUB     R5, R5, R7
        B       %BT35

42                              ;IF R9 short of total
        MOV     R7, R9, LSR R2
        SUB     LR, R1, R7
        CMPS    LR, #ScratchSpace
        LDRGTB  R0, [R1, R7]
        LDRGTB  LR, [R1,-R7]
        TEQGTS  R0, LR          ;AND unused gap of size R9 exists (GT preserves N=V=0)
        BLGT    %FT46           ;THEN exact fit with it
        B       %BT30

46
        RSB     R7, R9, #0
48
        MOV     R0, #MultiBit
        CMPS    R0, R6
50                                      ;corrupts R0, R3, R7, R9
; R0 measure of fit
; R7 fit type
;  0  just contiguous set of frags
;  +x miss out frag of size x
;  -x also use earlier frag of size x

        LDREQ   R9, FitType     ;if fit is same compare fit type
        CMPEQS  R7, R9
        BLS     %FT54
52
        MOVLO   R6, R0
        LDRLO   R3,PreFirstGap
        ASSERT  :INDEX: PreBestPtr = 4
        ASSERT  :INDEX: FitType    = :INDEX: PreBestPtr +4
        ASSERT  :INDEX: PtrDiff    = :INDEX: FitType +4
        STMLOIB  SP, {R3, R7, R9}
 [ DebugE
        BHS     %FT01
        DREG    R0, "multi fit - fit:",cc
        DREG    R3, ", pre:",cc
        DREG    R7, ", fit type:",cc
        DREG    R9, ", ptr diff:"
01
 ]
        MOVS    PC, LR

54
        Push    "R0, R1"
        LDR     R0, FirstGap+(2*4)      ;calc map ptr diff+zone diff*2^24
        LDR     R1, LastGap+(2*4)
        SUB     R9, R1, R0
        LDR     R3, [R10,#ZoneHead+SectorSize]
        ADD     R3, R3, #3              ;log2 bits in a zone
        MOV     R0, R0, LSR R3
        MOV     R1, R1, LSR R3
        SUB     R0, R1, R0              ;zone diff
        ORR     R9, R9, R0, LSL #24
        LDREQ   R3, PtrDiff+(2*4)
        CMPEQS  R9, R3
        Pull    "R0,R1"
        B       %BT52

58
        LDR     R3, AllocDir
        CMPS    R6 ,#-1
        MOVEQ   R0, #DiscFullErr
        BEQ     %FT88
        CMPS    R6, #MultiBit   ;only try pairs if wasting, crossing zone
        BEQ     %FT69           ;or multiple and fragmenting
        BLO     %FT89
59
 [ DebugE
        DLINE   "considering pairs"
 ]
        MOV     R7, #1
        LDRB    LR, [R10,#ZoneHead+SectorSize]
        MOV     R0, #8
        MOV     LR, R0, LSL LR  ;bits in zone
        CMPS    R4, LR
        MOVLS   R8, R4
        MOVLS   R5, #0
        MOVHI   R8, LR
        SUBHI   R5, LR, R4
        MOV     R8, R8, LSR R2
        MOV     R5, R5, LSR R2
	ADD	R9,R5,R8	; fix to prevent infinite loop if can't fit pair
	MOV	R9,R9,LSL R2
	CMP	R4,R9
	BGT	%FT70           ; end of fix
        B       %FT62

;R0 best short gap
;R1 -> freq tables
;R2 log2 alloc unit bit width
;R4 length required
;R5 short gap alloc units
;R6 old fit
;R7 fit*2
;R8 long gap alloc units

60
        LDRB    R9, [R1, R5]
        LDRB    LR, [R1, R8]
        MUL     LR, R9, LR      ;prefer pair with greatest frequency product
        CMPS    R7, LR, LSL #1
        MOVLS   R7, LR, LSL #1
        MOVLS   R0, R5, LSL R2
 [ DebugE
        BHI     %FT01
        DREG    R5, "pair fit - short gap:",cc
        DREG    R8, ", long gap:",cc
        DREG    R7, ", freq:"
01
 ]
62
        ADD     R5, R5, #1
        SUB     R8, R8, #1
        CMPS    R8, R5
        BHI     %BT60

        TEQS    R7, #1
        BEQ     %FT70           ;no pair found

        SUB     R4, R4, R0      ;size of larger
        MOV     R1, #NIL        ;pre smaller gap
        MOV     R6, #NIL        ;pre larger gap
        MOV     R11,#FreeLink*8
64
        BL      NextFree        ;(R10,R11->R9, R11,Z,C)
        BLNE    RdLenBits       ;(R10,R11->R7)
        BEQ     %FT70           ;amg: give up if we didn't find two suitable lumps
        TEQS    R7, R4           ;size = larger ?
        BNE     %FT66
        MOV     R6, R9
        TEQS    R1,#NIL
        BEQ     %BT64           ;loop if still looking for smaller
        Push    "R0,R1,R4,R6"    ;swap larger and smaller to share code
        Pull    "R4,R6"
        Pull    "R0,R1"
        B       %FT68
66
        TEQS    R7, R0           ;size = smaller ?
        BNE     %BT64
        MOV     R1, R9
        TEQS    R6,#NIL
        BEQ     %BT64           ;loop if still looking for larger
68
        BL      DefFindIdThenClaim ;(R3, R4, R6, R10->R2, R5, R11)
        MOV     R4, R0           ;size 2nd gap
        TEQS    R1, R11          ;was 1st predecessor of 2nd
        MOVNE   R6, R1           ;prev ptr for 2nd
        B       %FT75

69
        LDR     LR, PtrDiff
        CMPS    LR, #1 :SHL: 24
        LDRLO   LR, FitType
        CMPLOS  LR, #1 :SHL: 31
        BHI     %BT59
70
        TSTS    R6, #MultiBit
        BEQ     %FT89
        LDR     R5, FitType
        RSBS    R8, R5, #0
        BLE     %FT76

        SUB     R0, R4, R8        ;if using extra gap of size R8
        LDR     R2, PreBestPtr
        MOV     R11,#FreeLink*8
        B       %FT74

72
        TEQS    R7, R8
        MOVEQ   R6, R9
74
        BL      NextFree        ;(R10,R11->R9, R11,Z,C)
        BLNE    RdLenBits       ;(R10,R11->R7)
        CMPS    R11,R2
        BLS     %BT72
        MOV     R4, R8
        BL      DefFindIdThenClaim ;(R3,R4,R6,R10->R2,R5,R11,LR)
        MOV     R4, R0
        LDR     R6,PreBestPtr
75
        BL      DefChainClaim   ;(R2,R4-R6,R10->R5,R11,LR)
        B       %FT87

76
        LDR     R6, PreBestPtr
        BL      FindIdThenClaim    ;(R3-R5, R10->R2, R11)

87
        MOV     R0, #0
88
        ADD     SP, SP, #:INDEX:AllocWork2
        B       %FT93

89
        BIC     R6, R6, #WasteBit
        ADD     R1, R4, R6              ;gap length in map bits
        LDR     R6, PreBestPtr
        ADD     SP, SP, #:INDEX:AllocWork2
90
        BL      DefFindIdThenClaim      ;(R3,R4,R6,R10->R2,R5,R11)
        LDRB    LR, [R10,#ZoneHead+BitSize]
        MOV     R1, R1, LSL LR          ;gap size in bytes
        MOV     R8, R8, LSL LR          ;min map obj in bytes
        LDR     R0, [SP,#ClaimLength]
 [ BigShare
        BL      RoundUpShare            ;(R0,R3->R0)
 |
        BL      RoundUpSector           ;(R0,R3->R0)
 ]
        SUBS    LR, R1, R0              ;shared obj <=>
        CMPHIS  R8, LR                  ;(0<R1-R0<R8 AND R1<R8*2) OR R0<R8
        RSBHIS  LR, R1, R8, LSL #1
        CMPLSS  R8, R0
        ORRHI   R2, R2, #1              ;note shared obj
91
        MOV     R0, #0
93
        BL      SetVOnR0
95
        STRVS   R0, [SP]
        Pull    "R0,R1,R4-R11,PC"

 [ DebugFx
        MACRO
        CheckBastardMap $a,$b
        BL      CheckMapsOK
        BEQ     %FT01
        DREG    $a,$b
01
        MEND

CheckMapsOK ROUT
        Push    "r0-r9,r11,lr"
        MOV     r0, #0
10
        BL      InitZoneObj     ;(R0,R10->R8,R9,R11,LR)
        MOV     R5, LR
        MOV     R1, #-1
        MOV     R6, #0          ; not free prev

25
        BL      RdLenLinkBits   ;(R10,R11->R7,R8)
        TEQS    R11,R9          ;if gap
        BNE     %FT27
        TEQ     r6, #0          ; was free prev?
        BNE     %FT40
        MOV     r6, #-1         ; free was prev
        ADD     R9, R9, R8
        B       %FT30

27
        ; Is prev==this?, if yes map buggered
        TEQ     R8,R1
        BEQ     %FT40
        MOV     R1,R8
        MOV     r6, #0

30
        ADD     R11, R11, R7
        CMPS    R11, R5
        BLO     %BT25

        ADD     r0, r0, #1
        LDRB    lr, [r10, #ZoneHead + Zones]
        CMP     r0, lr
        BLO     %BT10

        Pull    "r0-r9,r11,pc"

40
        MOVS    r1, #-1
        Pull    "r0-r9,r11,pc"
 ]


NewRandomClaim ROUT

;entry
; R1 disc rec
; R3  dir
; R4  -> dir entry (if R11 = RandomAccessExtend )
; R10 size needed in bytes
; R11 RandomAccessCreate / RandomAccessExtend

;exit
; R2  ind disc add
; R10 actual size


        MOVS    R0, R10
        MOVMI   R0, #DiscFullErr
        BMI     %FT93
        BL      RoundUp                 ;(R0, R3->R0)
        LDRB    LR, [R1,#BitSize]
        MOV     R8, R0, LSR LR		; SBP: now have length in map bits
        Push    "R3,R8"

;TOTAL FREE AND CHOOSE ZONE FOR RandomAccessCreate, REGISTER USE

;R0 temp                R4 zone                 R8  best score
;R1 temp                R5 dir zone             R9  map ptr
;R2 best zone           R6 disc free            R10 map
;R3 zone free           R7 gap length           R11 map ptr

; SBP: 	Note, all the sizes used from here on appear to be in map
;	bits; this is A Good Thing.

        BL      CritInitReadNewFs       ;(->R10,R11)
 [ DebugFx
        CheckBastardMap r11, "Map bad on entry NewRandomClaim "
 ]
        MOV     R0, R3
        BL      IndDiscAddToZone	; (R0,R10->R0)
        MOV     R5, R0			; zone dir

        MOV     R2, #0	;  best zone=0
        MOV     R3, #0	;  zone free=0
        MOV     R4, #0	;       zone=0
        MOV     R6, #0	;  disc free=0
        MOV     R8, #0	; best score=0
05
        BL      NextFree        ;(R10,R11->R9, R11,Z,C)
        BLNE    RdLenBits       ;(R10,R11->R7)
        BCC     %FT10           ;branch if not zone end

        MOV     R9, PC          ;save flags
        MOV     R0, R3,LSL #19  ;calc score for this zone
        SUBS    R1, R4, R5
        SUBMI   R1, R5, R4
        ADD     R1, R1,#1
        BL      Divide  ;(ZoneFree *2^19)/( |Zone-DirZone|+1 ) (R0, R1->R0, R1)
        CMPS    R0, R8
        MOVHS   R8, R0          ;note score
        MOVHS   R2, R4          ;and zone if better

        LDRB    LR, [R10,#ZoneHead+SectorSize]
        MOV     R4, R11,LSR LR
        MOV     R4, R4, LSR #3  ;zone
        MOV     R3, #0          ;zone free = 0 for next zone
        TEQP    PC, R9          ;restore flags
10
        ADDNE   R3, R3, R7      ;zone free += gap size
        ADDNE   R6, R6, R7      ;disc free += gap size
        BNE     %BT05           ;loop while more gaps

        Pull    "R3, R8"

 [ DebugE
        DREG    R2, "OpenZone:",cc
        DREG    R6, ", DiscFree:",cc
        DREG    R8, ", SizeNeed:"
 ]

; R2  zone for create
; R3  dir (indirect disc addr)
; R6  disc free (map bits)
; R8  size needed (map bits)

        LDRB    R1, [R10,#ZoneHead+BitSize]
        LDR     LR, [SP,#ClaimReason]
        EORS    R4, LR, #RandomAccessCreate
        BNE     %FT15
; IF create THEN shuffle flag (R4) = FALSE
        BL      BytesPerCylinder        ;(R10->LR)
; SBP: R4=0
        SUB     R1, R4, LR, LSR R1 ; R1:=-(LR>>R1), so R1:=-map bits per cylinder
        MOV     R0, R2
        BL      DefCompactZone  ;(R0,R1,R10->R0,R2,V) do any compaction moves<cylinder
        BVS     %FT95
        MOV     R5, #0          ;old length = 0
        BL      InitZoneFree    ;start claiming from best zone start
        MOV     R1, #0          ;and not joining onto old end
        MOV     R2, #1          ;ind disc add for zero length files
        B       %FT20
15                              ;ELSE extend
        LDR     R4, [SP,#ClaimDirEntry]
        BL      ReadIndDiscAdd  ;(R3, R4->LR)
        MOV     R2, LR
        BL      ReadLen         ;(R4->LR)
        MOV     R0, LR
        BL      RoundUp         ;(R3, R0->R0)
        MOV     R1, R0, LSR R1
        SUB     R1, R1, #1
        MOV     R5, R1

; here, we're finding the disc fragment containing the end of the file

        BL      DefFindFragment ;(R1,R2,R10->R1,R9,R11,LR)
        ADD     R5, R5, LR      ;total allocated length in map bits
        CMPS    R8, R5		;compare wanted size with allocated size
        MOVLO   R8, R5		;if less, adjust up to allocated size
        ADD     R1, R1, LR      ;R1  points to next map block
        MOV     R0, R11		;R10 points to this map block

        MOV     R11,R9		;predecessor gap in R11
        Push    "R11"
        BL      NextFree        ;(R10,R11->R9,R10,R11,Z,C)
        MOVEQ   R11,#FreeLink*8 ;exhausted, back to start of zone
        BLEQ    NextFree        ;(R10,R11->R9,R10,R11,Z,C)
        TEQS    R11,R1
        Pull    "R11"
        MOVNE   R1, #0          ;R0=0->next free block not directly after us

        MOV     R4, #-1        ;shuffling may be necessary
20
        ADD     LR, R5, R6     ;allocated size + total free
        CMPS    R8, LR         ;wanted size > avail size?
        MOVHI   R0, #DiscFullErr  ; obvious, if there is no free space, bomb out
        BHI     %FT93

; if space allocated is sufficient, exit with success (via FT91)

        TEQS    R6, #0
        LDREQB  LR, [R10,#ZoneHead+BitSize]
        MOVEQ   R8, R8, LSL LR
        STREQ   R8, [SP,#ClaimLength]
        BEQ     %FT91          ; R2 is appropriate ind disc add

        MOV     R2, LR
 [ DebugE
        DREG    R0, "start:",cc
        DREG    R1, ", end:"
 ]

Stacked4        * 2*4
LastFrag4       * 0*4
LastEnd4        * 1*4
        Push    "R0, R1"         ;start and end of last frag if joining possible
        BL      BytesPerCylinder        ;(R10->LR)
        MOV     R1, LR
        LDRB    R0, [R10,#ZoneHead+RAskew]
        LDRB    LR, [R10,#ZoneHead+SectorSize]
        ADD     R0, R1, R0,LSL LR         ;bytes in (cylinder + RAskew) sectors

        LDRB    R7, [R10,#ZoneHead+BitSize]
25                             ;LOOP TO FIND ALLOC SIZE FOR RA FILES
        Push    "R0"
        BL      RoundUp                ;(R0,R3->R0)
        MOV     R9, R0, LSR R7
        Pull    "R0"                   ;round up and convert to alloc bits

        ADD     R0, R0, R1             ;add on a cylinder of bytes
        CMPS    R0, #&10000            ;IF <= 64K
        MOVLS   LR, R0, LSR R7
        CMPLSS  LR, R6, LSR #4         ;AND <= total free/16
        BLS     %BT25                  ;accept this size

        CMPS    R9, R6   ;MAX ALLOC SIZE
        MOVLO   R6, R9

; R2  max possible size (map bits)
; R3  dir
; R4  shuffle flag
; R5  total already allocated (map bits)
; R6  random access allocation unit (map bits)
; R8  size needed (map bits)
; R11 predecessor of gap to start claiming from (map bits)

 [ DebugE
        DREG    R5, "allocated:",cc
        DREG    R6, ", RA alloc:",cc
        DREG    R11, ", pre gap:"
 ]

Stacked4a       * 2*4
AllocTotal      * 0*4
PreClaim        * 1*4
        Push    "R5,R11"
; determine size to claim
        ADD     R0, R8, R6
        CMPS    R0, R2
        MOVHI   R0, R2
ShuffleBack
30
        BL      NextFree        ;(R10,R11->R9, R10,R11,Z,C)
        BLNE    RdLenBits       ;(R10,R11->R7)
 [ DebugE
        DREG    R0, "target:",cc
        DREG    R5, ", alloc:",cc
        BEQ     %FT01
        DREG    R7, ", gap len:",cc
        DREG    R11, ", map ptr:",cc
01
        DLINE   ""
 ]
        BCC     %FT35           ;not crossed zone

        MOVEQ   R11,#FreeLink*8
        BLEQ    NextFree        ;(R10,R11->R9, R10,R11,Z,C)
        BLNE    RdLenBits       ;(R10,R11->R7)
        TEQS    R4, #0          ;is shuffling down possible ?
        BNE     ShuffleDown

35
        ADD     R5, R5, R7	; is the gap big enough?
        CMPS    R5, R0
        BLO     %BT30		; if no, try next gap.

        SUB     R5, R5, R7
        SUB     R2, R0, R5
        CMPS    R5, R8          ;IF have found size needed already
        CMPHSS  R6, R2, LSL #1  ;AND more than half of extra extension found
        MOVHS   R0, R5          ;don't start fragmenting final gap
        BHS     %FT85

        BL      MinMapObj       ;(R10->LR)
        CMPS    R6, LR
        MOVHS   R9, R6
        MOVLO   R9, LR

        CMPS    R2, R9
        MOVLO   R2, R9
        BL      %FT75           ;check if to use all gap corrupts R0

        LDRB    LR, [R10,#ZoneHead+RAskew]
        TEQS    LR, #0
        BNE     %FT70
 ;Round up to cyl boundary if no RA skew
        ADD     R11,R11,R2
        BL      MapPtrToDiscAdd         ;(R3, R10,R11->R0)
        BIC     R0, R0,#DiscBits
 [ BigDisc
        BL      SectorsPerCylinder        ;(R10->LR)
        MOV     R1, LR
        BL      Divide
        TEQS    R1, #0			; R1=sector offset into cylinder
	BEQ	%FT65
        BL      SectorsPerCylinder      ; (R10->LR)
        SUB     R0, LR, R1              ; number of extra sectors
	LDRB	LR, [R10,#ZoneHead+SectorSize]	; back to bytes
	MOV	R0, R0, LSL LR
        BL      RoundUp           	;(R0, R3->R0)
        LDRB    LR, [R10,#ZoneHead+BitSize]
        ADD     R2, R2, R0,LSR LR       ;new size of block in map bits
65
 |
        BL	BytesPerCylinder        ;(R10->LR)
        MOV	R1, LR
        BL	Divide
        TEQS	R1, #0
	BEQ	%FT65
        BL	BytesPerCylinder        ;(R10->LR)
        SUB	R0, LR, R1
        BL	RoundUp                 ;(R0, R3->R0)
        LDRB	LR, [R10,#ZoneHead+BitSize]
        ADD	R2, R2, R0,LSR LR
65
 ]
70
        ADR     LR,%FT80
75
        ADD     R0, R2, R9
        CMPS    R0, R7
        MOVLS   PC, LR
        MOV     R2, R7
80
        ADD     R0, R5, R2
85
        LDR     LR, [SP,#Stacked4a+Stacked4+ClaimReason]
        TEQS    LR, #RandomAccessCreate
        LDRNE   R4, [SP,#Stacked4a+Stacked4+ClaimDirEntry]
        BLNE    ReadIndDiscAdd          ;(R3, R4->LR)
        MOVNE   R2, LR
        Pull    "R4,R6"			;
        SUB     R4, R0, R4

        BLEQ    DefFindIdThenClaim      ;(R3,R4,R6,R10->R2,R5,R11,LR)
        MOVEQ   R0, LR                  ;actual amount allocated
        TEQNES  R4, #0
        BLNE    DefChainClaim           ;(R2,R4,R6,R10->R5,R11,LR)
        SUBNE   R4, LR, R4              ;extra amount we weren't expecting
        ADDNE   R0, R0, R4              ;new length=length desired+extra amount
        LDRB    LR, [R10,#ZoneHead+BitSize]
        MOV     R0, R0, LSL LR
 [ DebugE :LOR: DebugEa
        DREG    R0, "new length:"
 ]
        STR     R0, [SP,#Stacked4+ClaimLength]

        Pull    "R1, R11"
        TEQNES  R11,#0
        BLNE    RdLenBits       ;(R10,R11->R7)
        ADDNE   R0, R11,R7
        SUBNE   R0, R0, R1
        BLNE    WrLenBits       ;(R0,R1,R10)
91
        MOV     R0,#0
93
        BL      SetVOnR0
95
ShuffleError
        STRVS   R0,[SP]
 [ DebugFx
        LDR     R11, [sp, #9*4]
        CheckBastardMap R11, "NewRandomClaim fucked up:"
 ]
        Pull    "R0,R1,R4-R11,PC"


; +++++++++++
; ShuffleDown
; +++++++++++

ShuffleDown ROUT

Stacked4b       * 3*4
        Push    "R0,R6,R8"
;FIND FIRST GAP AFTER FILE'S START ZONE

        LDR     R4, [SP,#Stacked4b+Stacked4a+Stacked4+ClaimDirEntry]
        BL      ReadIndDiscAdd  ;(R3,R4->LR)
        MOV     R2, LR
        MOV     R4, LR, LSL #8+1
        MOV     R4, R4, LSR #8+1+8      ;link bits
        MOV     R0, LR
        BL      IndDiscAddToZone        ;(R10,R0->R0)
        LDR     R5, [SP,#Stacked4b+AllocTotal]
        MOV     R1, R5
05
        BL      InitZoneObj     ;(R0, R10->R8, R9, R11,LR)
        STR     R8, [SP,#Stacked4b+PreClaim]
        MOV     R6, LR
10
        TEQS    R11, R9
        BEQ     %FT20           ;found a gap
        BL      RdLenLinkBits   ;(R10,R11-R7,R8)
        TEQS    R8, R4
        STREQ   R11,[SP,#Stacked4b+Stacked4a+LastFrag4]
        SUBEQS  R1, R1, R7
        BEQ     %FT15           ;reached end of file without finding any gaps
        ADD     R11,R11,R7
        CMPS    R11,R6
        BLO     %BT10           ;loop while more objects in zone

        ADD     R0, R0,#1
        LDRB    LR,[R10,#ZoneHead+Zones]
        CMPS    R0,LR
        MOVHS   R0,#0
        B        %BT05           ;loop for next zone

15
 [ DebugE
        DLINE   "no shuffling needed"
 ]
        ADD     R5,SP,#Stacked4b
        ASSERT  AllocTotal=0
        ASSERT  PreClaim=4
        LDMIA   R5,{R5, R11}
        B        %FT65

20
        SUB     R1, R5, R1      ;offset of gap in file in map bits
        LDRB    LR, [R10,#ZoneHead+BitSize]
        MOV     R5, R1, LSL LR  ;convert to bytes

        LDR     R8,[SP,#Stacked4b+Stacked4a+Stacked4+ClaimExt]
 [ DebugE
        DREG    R5, "gap offset:",cc
        DREG    R8, ", extent:"
 ]

Stacked4c       * 5*4
IndDiscAdd4c    * 1*4
LinkBits4c      * 3*4
        Push    "R1-R4,R11"
        SUBS    R2, R8, R5
        BLO     %FT60

        MOV     R0, #(1:SHL:UseScratchSpace) :OR: (1:SHL:UseSpareScreen) :OR: (1:SHL:UseWimpFree) :OR: (1:SHL:UseRmaHeap) :OR: (1:SHL:UseSysHeap) :OR: (1:SHL:UseIndOp) :OR: ScatterBit
        MOV     R1, #1
        LDRB    LR, [R10,#ZoneHead+SectorSize]
        MOV     R1, R1, LSL LR
        MOV     R3, R1
        CMPS    R2, R1
        MOVLO   R2, R1
        BL      FindBuffer      ;(R0-R3->R0-R3,V)
        BVS     %FT95

        MOV     R3, R2          ;buffer length
        MOV     R2, #-1         ;invalid dest ind disc add
        MOV     R6, #0          ;init bytes left from previous dest
        MOV     R9, R11         ;init next gap ptr
        MOV     R7, #0          ;init length last frag
25
        SUB     R4, R8, R5      ;If amount left to move
        CMPS    R4, R3          ;is > buffer length
        MOVHI   R4, R3          ;only move buffer length this time

        Push    "R2-R4"
        MOV     R1, #ReadSecsOp :OR: ScatterBit :OR: NoEscape
        LDR     R2, [SP,#3*4+IndDiscAdd4c]
        BL      InitScatter
        sbaddr  R3, ScatterList
        BL      GenIndDiscOp    ;(R1-R5->R0-R5,V)
        Pull    "R2-R4"
        BVS     %FT90

Stacked4d * 3*4
        Push    "R3,R5,R8"
        BL      InitScatter
        sbaddr  R3,ScatterList

        LDRB    LR, [R10,#ZoneHead+SectorSize]
        ADD     LR, LR ,#3              ;bits in a zone
        MOV     R5, R11,LSR LR          ;zone
        ADD     R5, R5, #1
        MOV     R5, R5, LSL LR          ;start next zone

        LDR     R1, [SP,#Stacked4d+IndDiscAdd4c]
        MOV     R1, R1, LSL #8+1
        MOV     R1, R1, LSR #8+1+8      ;link bits
30
        CMPS    R6,R4
        BHS     %FT55   ;if this dest can empty buffer
        B       %FT40

35
        LDRB    LR, [R10,#ZoneHead+SectorSize]
        SUB     R0, R11,R7
        MOV     R0, R0, LSR LR
        MOV     R0, R0, LSR #3
        ADD     R0, R0, #1
        LDRB    LR, [R10,#ZoneHead+Zones]
        CMPS    R0, LR
        MOVHSS  R0, #0

        BL      InitZoneObj     ;(R0,R10->R8,R9,R11,LR)
        MOV     R5, LR          ;next zone start
        B       %FT45

40
        ADD     R11,R11,R7
        CMPS    R11,R5
        BHS     %BT35
45
        BL      RdLenLinkBits   ;(R10,R11->R7,R8)
        TEQS    R11,R9          ;gap ?
        ADDEQ   R9, R11,R8      ;if so set next gap
        TEQNES  R8, R1
        BNE     %BT40

        Push    "R3"
        LDR     R3, [SP,#4+Stacked4d+IndDiscAdd4c]
        BL      MapPtrToDiscAdd  ;(R3,R10,R11->R0)
        Pull    "R3"
        LDRB    LR, [R10,#ZoneHead+BitSize]
        MOV     R8, R7, LSL LR

        ADDS    LR, R2, R6      ;V=0
        TEQS    LR, R0
        ADDEQ   R6, R6, R8
        BEQ     %BT30

        Push    "R1,R4"
        MOV     R1, #WriteSecsOp :OR: ScatterBit :OR: NoEscape
        MOVS    R4, R6
        BLNE    DoDiscOp        ;(R1-R4->R0-R4,V)
        Pull    "R1,R4"
        BVS     %FT85

        SUB     R4, R4, R6
        MOV     R2, R0
        MOV     R6, R8
        B       %BT30           ;loop if this dest wouldn't empty buffer
55
        SUB     R6, R6, R4
        MOV     R1, #WriteSecsOp :OR: ScatterBit :OR: NoEscape
        CMPS    R4, #0          ;V=0
        BLNE    DoDiscOp        ;(R1-R4->R0-R4,V)
        BVS     %FT85

        Pull    "R3,R5,R8"
        BVS     %FT90

        CMPS    R5, R8
        BLO     %BT25
        BL      ReturnBuffer

60
        Pull    "R1-R4,R9"
        MOV     R6, R1
        LDR     LR, [R10,#ZoneHead+BitSize]
        MOV     R0, R1, LSL LR

        LDR     R1, [SP,#Stacked4b+AllocTotal]
        MOV     R1, R1, LSL LR
        LDR     R4, [SP,#Stacked4b+Stacked4a+Stacked4+ClaimDirEntry]
        LDR     R5, [SP,#Stacked4b+Stacked4a+Stacked4+ClaimDirStart]
        BL      ReturnSpace     ;(R0,R1,R2,R3,R4,R5)

        MOV     R5, R6          ;new allocated length in map bits
        STR     R5, [SP,#Stacked4b+AllocTotal]

        LDR     R11,[SP,#Stacked4b+Stacked4a+LastFrag4]
        BL      RdLenBits       ;(R10,R11->R7)
        ADD     R11,R11,R7

        TEQS    R11,R9          ;does end of last frag join next gap ?
        MOVNE   R11,#0
        STR     R11,[SP,#Stacked4b+Stacked4a+LastEnd4]
        LDR     R11,[SP,#Stacked4b+PreClaim]

65
        Pull    "R0,R6,R8"
 [ DebugFx
        CheckBastardMap R11, "NewRandomClaim shuffle down up:"
 ]
        MOV     R4, #0
        B       ShuffleBack

85
        ADD     SP, SP, #Stacked4d
90
        BL      ReturnBuffer
95
        ADD     SP, SP, #Stacked4c+Stacked4b+Stacked4a+Stacked4
        B       ShuffleError


; ================
; BytesPerCylinder
; ================

;entry R10 -> new map

;exit  lr bytes in a cylinder

BytesPerCylinder
        Push    "R0,LR"
        LDRB    R0,[R10,#ZoneHead+SecsPerTrk]
        LDRB    LR,[R10,#ZoneHead+Heads]
        MUL     LR,R0,LR                ;sectors per cylinder
        LDRB    R0,[R10,#ZoneHead+SectorSize]
        MOV     LR,LR,LSL R0            ;convert to bytes
 [ DebugE
        Push    "R0"
        MOV     R0, LR
        DREG    R0, "BytesPerCylinder:"
        Pull    "R0"
 ]
        Pull    "R0,PC"


; ================
; SectorsPerCylinder
; ================

;entry R10 -> new map

;exit  lr sectors in a cylinder

SectorsPerCylinder
        Push    "R0,LR"
        LDRB    R0,[R10,#ZoneHead+SecsPerTrk]
        LDRB    LR,[R10,#ZoneHead+Heads]
        MUL     LR,R0,LR                ;sectors per cylinder

 [ DebugE
        Push    "R0"
        MOV     R0, LR
        DREG    R0, "SectorsPerCylinder:"
        Pull    "R0"
 ]
        Pull    "R0,PC"

; =======
; SortDir
; =======

; form table in scratch space for each object small enough to share a map obj
; bits 0-7   0=>dir itself, else index of obj in dir
; bits 8-15  are sector offset in shared block
; bit  16    set if link bits >= link bits for dir
; bits 17-31 are link bits

;entry
; R3    disc address of dir
; R5 -> dir start

;exit
; R8 -> table start, table end marked by 0 word

SortDir ROUT                    ;BUILD TABLE
 [ DebugE
        DREG    R3, "SortDir(",cc
        DREG    R5, ",",cc
        DLINE   ")"
 ]
        Push    "R0-R2,R4,R7,LR"
        MOV     R1, #0                  ;init index in dir
        MOV     R8, #ScratchSpace
        MOV     R7, R8
        ANDS    LR, R3, #&FF
        MOVNE   LR, LR, LSL #8
        ORRNE   LR, LR, #1 :SHL: 16
        STRNE   LR, [R7],#4
        SUB     R4, R5, #NewDirEntrySz-DirFirstEntry
        B       %FT10
05
        ADD     R1, R1, #1              ;inc dir index
        BL      ReadIntAtts             ;(R3,R4->LR)
        TSTS    LR, #DirBit
        BNE     %FT10
        BL      ReadIndDiscAdd          ;(R3,R4->LR)
        BIC     R2, LR, #DiscBits
        TEQS    R2, #1                  ;skip if 0 length
        ANDNES  R2, LR, #&FF            ;or not shared
        BEQ     %FT10
        MOV     LR, LR, LSR #8          ;build entry
        SUBS    LR, LR, R3, LSR #8
        RSBMI   LR, LR, #0
        ORR     LR, R1, LR, LSL #17
        ORRPL   LR, LR, #1 :SHL: 16
        ORR     LR, LR, R2, LSL #8
        STR     LR, [R7],#4
10
        LDRB    LR, [R4,#NewDirEntrySz]!
        CMPS    LR, #" "
        BHI     %BT05

        MOV     R0, R8
        MOV     R1, R7
        BL      Sort            ;(R0, R1)
        MOV     LR, #0
        STR     LR, [R7]
        Pull    "R0-R2,R4,R7,PC",,^

 ]

        LTORG
        END
